package 分治回溯.迷宫;

import 动态链表.LinkedList;

public class Maze {
    private static int[][] maze = {
            {1, 1, 1, 1, 1, 1, 1, 1, 1},
            {0, 0, 1, 0, 0, 0, 1, 1, 1},
            {1, 0, 1, 1, 1, 0, 1, 1, 1},
            {1, 0, 0, 1, 0, 0, 1, 1, 1},
            {1, 1, 0, 1, 1, 0, 0, 0, 1},
            {1, 0, 0, 0, 0, 0, 1, 0, 1},
            {1, 0, 1, 1, 1, 0, 0, 0, 1},
            {1, 1, 0, 0, 0, 0, 1, 0, 0},
            {1, 1, 1, 1, 1, 1, 1, 1, 1}
    };
    private static int enterX = 1;
    private static int enterY = 0;
    private static int exitX = 7;
    private static int exitY = 8;
    private static boolean[][] visited = new boolean[9][9];
    private static int[][] direction = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    private static LinkedList<String> list = new LinkedList<>();

    public static void main(String[] args) {
        if (go(enterX,enterY)){
            list.forEach(System.out::println);
        }else {
            System.out.println("走不通！");
        }
    }

    private static boolean go(int x, int y) {
        list.push("("+x+","+y+")");
        visited[x][y] = true;
        if (x == exitX && y == exitY){
            return true;
        }
        for (int i = 0; i < direction.length; i++) {
            int newX = x + direction[i][0];
            int newY = y + direction[i][1];
            if (isInArea(newX,newY) && isRoad(newX,newY) && !visited[newX][newY]){
                if (go(newX,newY)){
                    return true;
                }
            }
        }
        list.pop();
        return false;
    }

    private static boolean isRoad(int x, int y) {
        return maze[x][y] == 0;
    }

    private static boolean isInArea(int x, int y) {
        return x >= 0 && x < 9 && y >= 0 && y < 9;
    }

}
